package algorithm;

import java.util.Arrays;

/**
 * 743. 网络延迟时间
 * n个节点，k为源节点
 * 单源节点最短路劲
 * @param：int[][] g = new int[n][n] 表示
 */
public class LeetCode_networkDelayTime_743 {
    public int networkDelayTime(int[][] times, int n, int k) {
        final int INM = Integer.MAX_VALUE / 2;
        // 使用一个二维数组记录times中记录的可达节点之间的距离
        int[][] g = new int[n][n];

        for (int i = 0 ; i < n ; ++i) {
            Arrays.fill(g[i], INM);
        }
        // 把可达的节点之间的真实距离保存下来
        for (int[] t : times) {
            // 我们让边序号从0开始
            int x = t[0] - 1, y = t[1] - 1;
            g[x][y] = t[2];
        }
        // 记录从源节点到某个节点的最短距离
        int[] dist = new int[n];
        Arrays.fill(dist, INM);
        // k为源节点，源节点的距离位置为0
        dist[k - 1] = 0;

        // 建立一个“节点是否被遍历”的标志
        boolean[] used = new boolean[n];

        for (int i = 0 ; i < n ; ++i) {
            // 开始遍历节点，从还没遍历过的节点中找出距离最短的节点路径
            // 小技巧：设置x=-1，可以保证第一个遍历到的一定是k节点
            int x = -1;
            // 遍历节点，y是位置
            for (int y = 0 ; y < n ; ++y) {
                // 因为dist[k - 1] == 0，所以在下面的判断中，结束这个for循环之后，得到的第一个x一定是k节点
                if (!used[y] && (x == -1 || dist[y] < dist[x])) {
                    x = y;
                }
            }
            // 出来之后的x就是遍历过了，找到了到下一个节点的最短路径
            used[x] = true;

            // 开始计算是否需要更换最短路径值
            for (int y = 0 ; y < n ; ++y) {
                // dist[y]是当前x节点的前一个节点走过y节点的距离
                dist[y] = Math.min(dist[y], dist[x] + g[x][y]);
            }

        }
        int res = Arrays.stream(dist).max().getAsInt();
        return res == INM ? -1 : res;
    }
}
